package java_0220.leetcode;

/**
 * 根据二叉树前序和中序还原二叉树
 */
public class Num105_BuildTreeByPreAndIn {
    //当前处理到前序结果集的哪个节点
    private int index=0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //TreeNode深度范围在1-3000之间，不用判空
        return buildTreeHelper( preorder, inorder, 0, preorder.length-1);
    }

    /**
     * 在preOrder的[left,right]借助中序遍历还原二叉树，返回二叉树的根节点
     * @param preorder
     * @param inorder
     * @param left
     * @param right
     * @return
     */

    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        //边界
        if(left>right){
           //空区间
            return null;
        }
        if(index==preorder.length){
            //此时前序遍历结束，前序遍历结果集已经处理完毕
            return null;
        }
        //构建根节点
        TreeNode root=new TreeNode(preorder[index]);
        index++;
        //找到该节点在中序遍历的索引位置
        int pos=find(root.val,inorder);
        //根据中序遍历的位置知道树的左侧在哪右侧在哪
        root.left=buildTreeHelper(preorder,inorder,left,pos-1);
        root.right=buildTreeHelper(preorder,inorder,pos+1,right);
        return root;
    }

    /**
     * 找到val这个值在中序遍历的索引位置
     * @param val
     * @param inorder
     * @return
     */
    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }
}
